package BinaryTree;

import java.util.Stack;

class Convert {
    TreeNode pre = null;
    TreeNode root = null;
    public TreeNode Convert1(TreeNode pRootOfTree) {

        //中序遍历 记录前一个节点
        if(pRootOfTree==null){
            return null;
        }
        Convert1(pRootOfTree.left);
        if(root==null){
            root = pRootOfTree;
        }
        if(pre!=null){

            pRootOfTree.left = pre;
            pre.right = pRootOfTree;

        }
        pre = pRootOfTree;
        Convert1(pRootOfTree.right);
        return root;
    }

    //     迭代法中序遍历
    public static TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        TreeNode head = pRootOfTree;  //当前头
        TreeNode tmp = null;  //前一个节点
        Stack<TreeNode> stack = new Stack<>();
        //中序遍历逻辑
        while (head != null || !stack.empty()) {
            if (head != null) {
                stack.push(head);
                head = head.left;
            } else {
                TreeNode pop = stack.pop();
                if(tmp==null){
                    //为空说明是第一个节点
                    head = pop;
                }else{  //如果前一个节点不为空，连接起来
                    tmp.right = pop;
                    pop.left = tmp;
                }

                tmp = pop;  //更新前一个节点
                head = head.right;
            }
        }
        //找回首节点，最后tmp是在双向链表的末尾
        while (tmp.left != null) {
            tmp = tmp.left;
        }
        return tmp;
    }
}
